SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Assignment problem</title>

</head>

Assignment problem

</h1>

</header>

The assignment problem is a fundamental <a href="Combinatorial_optimization" title="Combinatorial optimization">combinatorial optimization</a> problem. In its most general form, the problem is as follows:

<dl><dd>The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized.</dd></dl>

Alternatively, describing the problem using graph theory:

<dl><dd>The assignment problem consists of finding, in a <a href="Weighted_graph" class="mw-redirect" title="Weighted graph">weighted</a> <a href="Bipartite_graph" title="Bipartite graph">bipartite graph</a>, a <a href="Matching_(graph_theory)" title="Matching (graph theory)">matching</a> of maximum size, in which the sum of weights of the edges is minimum.</dd></dl>

If the numbers of agents and tasks are equal, then the problem is called balanced assignment, and the graph-theoretic version is called minimum-cost perfect matching. Otherwise, it is called unbalanced assignment.<a href="#cite_note-:0-1">[1]</a>

If the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called linear assignment. Commonly, when speaking of the assignment problem without any additional qualification, then the linear balanced assignment problem is meant.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. This is a balanced assignment problem. Its solution is whichever combination of taxis and customers results in the least total cost.

Now, suppose that there are four taxis available, but still only three customers. This is an unbalanced assignment problem. One way to solve it is to invent a fourth dummy task, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. This reduces the problem to a balanced assignment problem, which can then be solved in the usual way and still give the best solution to the problem.

Similar adjustments can be done in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

The formal definition of the assignment problem (or linear assignment problem) is

<dl><dd>Given two sets, A and T, together with a <a href="Weight_function" title="Weight function">weight function</a> C : A × T → <a href="Real_number" title="Real number">R</a>. Find a <a href="Bijection" title="Bijection">bijection</a> f : A → T such that the <a href="Loss_function" title="Loss function">cost function</a>:

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{a\in A}C(a,f(a))}</annotation>

</semantics>

</math><img src="./16b7eda822426d7a5f813f22e4905432c4ba79ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:13.899ex; height:5.676ex;" alt="{\displaystyle \sum _{a\in A}C(a,f(a))}" loading="lazy"></dd></dl></dd>

<dd>is minimized.</dd></dl>

Usually the weight function is viewed as a square real-valued <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> C, so that the cost function is written down as:

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{a\in A}C_{a,f(a)}}</annotation>

</semantics>

</math><img src="./3f06886751101bfff9065533c5c9f2d755ac2148.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:10.016ex; height:5.676ex;" alt="{\displaystyle \sum _{a\in A}C_{a,f(a)}}" loading="lazy"></dd></dl>

The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

A naive solution for the assignment problem is to check all the assignments and calculate the cost of each one. This may be very inefficient since, with n agents and n tasks, there are n! (<a href="Factorial" title="Factorial">factorial</a> of n) different assignments.

Another naive solution is to greedily assign the pair with the smallest cost first, and remove the vertices; then, among the remaining vertices, assign the pair with the smallest cost; and so on. This algorithm may yield a non-optimal solution. For example, suppose there are two tasks and two agents with costs as follows:

<ul><li>Alice: Task 1 = 1, Task 2 = 2.</li>

<li>George: Task 1 = 5, Task 2 = 8.</li></ul>

The greedy algorithm would assign Task 1 to Alice and Task 2 to George, for a total cost of 9; but the reverse assignment has a total cost of 7.

Fortunately, there are many algorithms for finding the optimal assignment in time <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial</a> in n. The assignment problem is a special case of the <a href="Transportation_problem" class="mw-redirect" title="Transportation problem">transportation problem</a>, which is a special case of the <a href="Minimum_cost_flow_problem" class="mw-redirect" title="Minimum cost flow problem">minimum cost flow problem</a>, which in turn is a special case of a <a href="Linear_program" class="mw-redirect" title="Linear program">linear program</a>. While it is possible to solve any of these problems using the <a href="Simplex_algorithm" title="Simplex algorithm">simplex algorithm</a>, or in worst-case polynomial time using the <a href="Ellipsoid_method" title="Ellipsoid method">ellipsoid method</a>, each specialization has a smaller solution space and thus more efficient algorithms designed to take advantage of its special structure.

<div class="mw-heading mw-heading3"><h3 id="Balanced_assignment">Balanced assignment</h3></div>

In the balanced assignment problem, both parts of the bipartite graph have the same number of vertices, denoted by n.

One of the first polynomial-time algorithms for balanced assignment was the <a href="Hungarian_algorithm" title="Hungarian algorithm">Hungarian algorithm</a>. It is a global algorithm – it is based on improving a matching along augmenting paths (alternating paths between unmatched vertices). Its run-time complexity, when using <a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heaps</a>, is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn+n^{2}\log n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn+n^{2}\log n)}</annotation>

</semantics>

</math><img src="./e6c65ba1ec52875d490e86d8eed282c87ce738a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.448ex; height:3.176ex;" alt="{\displaystyle O(mn+n^{2}\log n)}" loading="lazy">,<a href="#cite_note-2">[2]</a> where m is a number of edges. This is currently the fastest run-time of a <a href="Strongly_polynomial" class="mw-redirect" title="Strongly polynomial">strongly polynomial</a> algorithm for this problem. Some variants of the Hungarian algorithm also benefit from parallel computing, including GPU acceleration.<a href="#cite_note-3">[3]</a> If all weights are integers, then the run-time can be improved to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mn+n^{2}\log \log n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mn+n^{2}\log \log n)}</annotation>

</semantics>

</math><img src="./c8661bb2aae62d3f69c0b65e6b3a7abc1a6604c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.807ex; height:3.176ex;" alt="{\displaystyle O(mn+n^{2}\log \log n)}" loading="lazy">, but the resulting algorithm is only weakly-polynomial.<a href="#cite_note-4">[4]</a> If the weights are integers, and all weights are at most C (where C>1 is some integer), then the problem can be solved in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m{\sqrt {n}}\log(n\cdot C))}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(m{\sqrt {n}}\log(n\cdot C))}</annotation>

</semantics>

</math><img src="./4b22cc76eb3e123874160f7726485fad7410a840.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.962ex; height:3.009ex;" alt="{\displaystyle O(m{\sqrt {n}}\log(n\cdot C))}" loading="lazy"> weakly-polynomial time in a method called weight scaling.<a href="#cite_note-5">[5]</a><a href="#cite_note-6">[6]</a><a href="#cite_note-7">[7]</a>

In addition to the global methods, there are local methods which are based on finding local updates (rather than full augmenting paths). These methods have worse asymptotic runtime guarantees, but they often work better in practice. These algorithms are called <a href="Auction_algorithm" title="Auction algorithm">auction algorithms</a>, push-relabel algorithms, or preflow-push algorithms. Some of these algorithms were shown to be equivalent.<a href="#cite_note-8">[8]</a>

Some of the local methods assume that the graph admits a perfect matching; if this is not the case, then some of these methods might run forever.<a href="#cite_note-:0-1">[1]</a>: 3 A simple technical way to solve this problem is to extend the input graph to a complete bipartite graph, by adding artificial edges with very large weights. These weights should exceed the weights of all existing matchings, to prevent appearance of artificial edges in the possible solution.

As shown by Mulmuley, Vazirani and Vazirani,<a href="#cite_note-9">[9]</a> the problem of minimum weight perfect matching is converted to finding minors in the <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a> of a graph. Using the <a href="Isolation_lemma" title="Isolation lemma">isolation lemma</a>, a minimum weight perfect matching in a graph can be found with probability at least <style data-mw-deduplicate="TemplateStyles:r1154941027">

/* start https://en.wikipedia.org/ */

.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>1⁄2. For a graph with n vertices, it requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{2}(n))}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{2}(n))}</annotation>

</semantics>

</math><img src="./3504e9a0325bc9a82cfe4889213e0c3008dd1b54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.813ex; height:3.176ex;" alt="{\displaystyle O(\log ^{2}(n))}" loading="lazy"> time.

<div class="mw-heading mw-heading3"><h3 id="Unbalanced_assignment">Unbalanced assignment</h3></div>

In the unbalanced assignment problem, the larger part of the bipartite graph has n vertices and the smaller part has r<n vertices. There is also a constant s which is at most the cardinality of a maximum matching in the graph. The goal is to find a minimum-cost matching of size exactly s. The most common case is the case in which the graph admits a one-sided-perfect matching (i.e., a matching of size r), and s=r.

Unbalanced assignment can be reduced to a balanced assignment. The naive reduction is to add <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-r}</annotation>

</semantics>

</math><img src="./86c0aa8d9c52b096540edd6e6a91eb8f790a8b7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.284ex; height:2.176ex;" alt="{\displaystyle n-r}" loading="lazy"> new vertices to the smaller part and connect them to the larger part using edges of cost 0. However, this requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n(n-r)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n(n-r)}</annotation>

</semantics>

</math><img src="./137dd4aae523a75f5dd223b67951b0b8eab6f324.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.488ex; height:2.843ex;" alt="{\displaystyle n(n-r)}" loading="lazy"> new edges. A more efficient reduction is called the doubling technique. Here, a new graph G' is built from two copies of the original graph G: a forward copy Gf and a backward copy Gb. The backward copy is "flipped", so that, in each side of G', there are now n+r vertices. Between the copies, we need to add two kinds of linking edges:<a href="#cite_note-:0-1">[1]</a>: 4–6

<ul><li>Large-to-large: from each vertex in the larger part of Gf, add a zero-cost edge to the corresponding vertex in Gb.</li>

<li>Small-to-small: if the original graph does not have a one-sided-perfect matching, then from each vertex in the smaller part of Gf, add a very-high-cost edge to the corresponding vertex in Gb.</li></ul>

All in all, at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+r}</annotation>

</semantics>

</math><img src="./d6a5e6925440ca0c67b8608c15b3fc842d6b3199.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.284ex; height:2.176ex;" alt="{\displaystyle n+r}" loading="lazy"> new edges are required. The resulting graph always has a perfect matching of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+r}</annotation>

</semantics>

</math><img src="./d6a5e6925440ca0c67b8608c15b3fc842d6b3199.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.284ex; height:2.176ex;" alt="{\displaystyle n+r}" loading="lazy">. A minimum-cost perfect matching in this graph must consist of minimum-cost maximum-cardinality matchings in Gf and Gb. The main problem with this doubling technique is that there is no speed gain when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\ll n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\ll n}</annotation>

</semantics>

</math><img src="./d2e3eba9748707971ca5eff9ebdd7367035a18c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.057ex; height:1.843ex;" alt="{\displaystyle r\ll n}" loading="lazy">.

Instead of using reduction, the unbalanced assignment problem can be solved by directly generalizing existing algorithms for balanced assignment. The <a href="Hungarian_algorithm" title="Hungarian algorithm">Hungarian algorithm</a> can be generalized to solve the problem in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(ms+s^{2}\log r)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(ms+s^{2}\log r)}</annotation>

</semantics>

</math><img src="./643abc1cc3b267708c031535dacebaea3763f1ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.493ex; height:3.176ex;" alt="{\displaystyle O(ms+s^{2}\log r)}" loading="lazy"> strongly-polynomial time. In particular, if s=r then the runtime is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mr+r^{2}\log r)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mr+r^{2}\log r)}</annotation>

</semantics>

</math><img src="./2d539da2c847e451f6ffffd2c27224aab018c6b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.41ex; height:3.176ex;" alt="{\displaystyle O(mr+r^{2}\log r)}" loading="lazy">. If the weights are integers, then Thorup's method can be used to get a runtime of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(ms+s^{2}\log \log r)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(ms+s^{2}\log \log r)}</annotation>

</semantics>

</math><img src="./f91967a0cd5e7e446df7e713569c23afe3548ee1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.852ex; height:3.176ex;" alt="{\displaystyle O(ms+s^{2}\log \log r)}" loading="lazy">.<a href="#cite_note-:0-1">[1]</a>: 6

<div class="mw-heading mw-heading3"><h3 id="Solution_by_linear_programming">Solution by linear programming</h3></div>

The assignment problem can be solved by presenting it as a <a href="Linear_program" class="mw-redirect" title="Linear program">linear program</a>. For convenience we will present the maximization problem. Each edge (i,j), where i is in A and j is in T, has a weight <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle w_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle w_{ij}}</annotation>

</semantics>

</math><img src="./7250b6181b9bba7a8edf5845fb59dfc7fe1f722f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.141ex; height:2.343ex;" alt="{\textstyle w_{ij}}" loading="lazy">. For each edge ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i,j)}</annotation>

</semantics>

</math><img src="./8ef21910f980c6fca2b15bee102a7a0d861ed712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.604ex; height:2.843ex;" alt="{\displaystyle (i,j)}" loading="lazy">⁠ we have a variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle x_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle x_{ij}}</annotation>

</semantics>

</math><img src="./a350feefa817472ab65b8e836c3149be3cffedf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.807ex; height:2.343ex;" alt="{\textstyle x_{ij}}" loading="lazy">. The variable is 1 if the edge is contained in the matching and 0 otherwise, so we set the domain constraints:

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,}</annotation>

</semantics>

</math> <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}</annotation>

</semantics>

</math>

The total weight of the matching is: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{(i,j)\in A\times T}w_{ij}x_{ij}}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{(i,j)\in A\times T}w_{ij}x_{ij}}</annotation>

</semantics>

</math><img src="./e1de09cfde145ed0c829f6ccfd701a6db67e8cab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:14.081ex; height:6.009ex;" alt="{\displaystyle \sum _{(i,j)\in A\times T}w_{ij}x_{ij}}" loading="lazy">. The goal is to find a maximum-weight perfect matching.

To guarantee that the variables indeed represent a perfect matching, we add constraints saying that each vertex is adjacent to exactly one edge in the matching, i.e.,

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T,\,}</annotation>

</semantics>

</math>.

All in all we have the following LP:

<mtext>maximize</mtext>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{maximize}}~~\sum _{(i,j)\in A\times T}w_{ij}x_{ij}}</annotation>

</semantics>

</math><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{subject to}}~~\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T}">

<mtext>subject to</mtext>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{subject to}}~~\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T}</annotation>

</semantics>

</math><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,}</annotation>

</semantics>

</math><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}</annotation>

</semantics>

</math>This is an integer linear program. However, we can solve it without the integrality constraints (i.e., drop the last constraint), using standard methods for solving continuous linear programs. While this formulation allows also fractional variable values, in this special case, the LP always has an optimal solution where the variables take integer values. This is because the constraint matrix of the fractional LP is <a href="Unimodular_matrix#Total_unimodularity" title="Unimodular matrix">totally unimodular</a> – it satisfies the four conditions of Hoffman and Gale.

<div class="mw-heading mw-heading3"><h3 id="Other_methods_and_approximation_algorithms">Other methods and approximation algorithms</h3></div>

Other approaches for the assignment problem exist and are reviewed by Duan and Pettie<a href="#cite_note-10">[10]</a> (see Table II). Their work proposes an <a href="Approximation_algorithm" title="Approximation algorithm">approximation algorithm</a> for the assignment problem (and the more general <a href="Maximum_weight_matching" title="Maximum weight matching">maximum weight matching</a> problem), which runs in linear time for any fixed error bound.

<div class="mw-heading mw-heading2"><h2 id="Many-to-many_assignment">Many-to-many assignment</h2></div>

In the basic assignment problem, each agent is assigned to at most one task and each task is assigned to at most one agent. In the many-to-many assignment problem,<a href="#cite_note-11">[11]</a> each agent i may take up to ci tasks (ci is called the agent's capacity), and each task j may be taken by up to dj agents simultaneously (dj is called the task's capacity). If the sums of capacities in both sides are equal (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i}c_{i}=\sum _{j}d_{j}}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i}c_{i}=\sum _{j}d_{j}}</annotation>

</semantics>

</math><img src="./833982e6f9c80bdd2ab3af9be9ca297024d61796.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:14.508ex; height:5.843ex;" alt="{\displaystyle \sum _{i}c_{i}=\sum _{j}d_{j}}" loading="lazy">), then the problem is balanced, and the goal is to find a perfect matching (assign exactly ci tasks to each agent i and exactly dj agents to each task j) such that the total cost is as small as possible.

The problem can be solved by reduction to the <a href="Network_flow_problem" title="Network flow problem">minimum cost network flow problem</a>.<a href="#cite_note-12">[12]</a> Construct a flow network with the following layers:

<ul><li>Layer 1: One source-node s.</li>

<li>Layer 2: a node for each agent. There is an arc from s to each agent i, with cost 0 and capacity ci .</li>

<li>Level 3: a node for each task. There is an arc from each agent i to each task j, with the corresponding cost, and capacity 1.</li>

<li>Level 4: One sink-node t. There is an arc from each task to t, with cost 0 and capacity dj.</li></ul>

An integral maximum flow of minimum cost can be found in polynomial time; see <a href="Network_flow_problem" title="Network flow problem">network flow problem</a>. Every integral maximum flow in this network corresponds to a matching in which at most ci tasks are assigned to each agent i and at most dj agents are assigned to each task j (in the balanced case, exactly ci tasks are assigned to i and exactly dj agents are assigned to j). A min-cost maximum flow corresponds to a min-cost assignment.

<div class="mw-heading mw-heading2"><h2 id="Generalization">Generalization</h2></div>

When phrased as a graph theory problem, the assignment problem can be extended from <a href="Bipartite_graph" title="Bipartite graph">bipartite graphs</a> to arbitrary graphs. The corresponding problem, of finding a <a href="Matching_(graph_theory)" title="Matching (graph theory)">matching</a> in a <a href="Weighted_graph" class="mw-redirect" title="Weighted graph">weighted graph</a> where the sum of weights is maximized, is called the <a href="Maximum_weight_matching" title="Maximum weight matching">maximum weight matching problem</a>.

Another generalization of the assignment problem is extending the number of sets to be matched from two to many. So that rather than matching agents to tasks, the problem is extended to matching agents to tasks to time intervals to locations. This results in <a href="Multidimensional_assignment_problem_(MAP)" class="mw-redirect" title="Multidimensional assignment problem (MAP)">Multidimensional assignment problem (MAP)</a>.

<ul><li><a href="Auction_algorithm" title="Auction algorithm">Auction algorithm</a></li>

<li><a href="Generalized_assignment_problem" title="Generalized assignment problem">Generalized assignment problem</a></li>

<li><a href="Linear_bottleneck_assignment_problem" title="Linear bottleneck assignment problem">Linear bottleneck assignment problem</a></li>

<li><a href="Monge-Kantorovich_transportation_problem" class="mw-redirect" title="Monge-Kantorovich transportation problem">Monge-Kantorovich transportation problem</a>, a more general formulation</li>

<li><a href="National_Resident_Matching_Program" title="National Resident Matching Program">National Resident Matching Program</a></li>

<li><a href="Quadratic_assignment_problem" title="Quadratic assignment problem">Quadratic assignment problem</a></li>

<li><a href="Rank-maximal_matching" class="mw-redirect" title="Rank-maximal matching">Rank-maximal matching</a></li>

<li><a href="Secretary_problem" title="Secretary problem">Secretary problem</a></li>

<li><a href="Stable_matching_problem" title="Stable matching problem">Stable matching problem</a></li>

<li><a href="Stable_roommates_problem" title="Stable roommates problem">Stable roommates problem</a></li>

<li><a href="Weapon_target_assignment_problem" title="Weapon target assignment problem">Weapon target assignment problem</a></li>

<li><a href="House_allocation_problem" title="House allocation problem">House allocation problem</a></li>

<li><a href="Multidimensional_assignment_problem_(MAP)" class="mw-redirect" title="Multidimensional assignment problem (MAP)">Multidimensional assignment problem (MAP)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References_and_further_reading">References and further reading</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLyle_Ramshaw,_Robert_E._Tarjan2012" class="citation web cs1">Lyle Ramshaw, Robert E. Tarjan (2012). <a rel="nofollow" class="external text" href="https://www.labs.hpe.com/techreports/2012/HPL-2012-40.pdf">"On minimum-cost assignments in unbalanced bipartite graphs"</a> (PDF). HP research labs.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFFredmanTarjan1987" class="citation journal cs1">Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F28869.28874">"Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms"</a>. J. ACM. 34 (3): 596–615. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F28869.28874">10.1145/28869.28874</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7904683">7904683</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFKawtikwarNagi2024" class="citation journal cs1">Kawtikwar, Samiran; Nagi, Rakesh (2024-05-01). <a rel="nofollow" class="external text" href="https://linkinghub.elsevier.com/retrieve/pii/S0743731524000029">"HyLAC: Hybrid linear assignment solver in CUDA"</a>. Journal of Parallel and Distributed Computing. 187: 104838. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jpdc.2024.104838">10.1016/j.jpdc.2024.104838</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0743-7315">0743-7315</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFThorup2004" class="citation journal cs1">Thorup, Mikkel (2004-11-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2004.04.003">"Integer priority queues with decrease key in constant time and the single source shortest paths problem"</a>. Journal of Computer and System Sciences. Special Issue on STOC 2003. 69 (3): 330–353. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2004.04.003">10.1016/j.jcss.2004.04.003</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-0000">0022-0000</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFGabowTarjan1989" class="citation journal cs1">Gabow, H.; Tarjan, R. (1989-10-01). "Faster Scaling Algorithms for Network Problems". SIAM Journal on Computing. 18 (5): 1013–1036. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0218069">10.1137/0218069</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFGoldbergKennedy1997" class="citation journal cs1">Goldberg, A.; Kennedy, R. (1997-11-01). "Global Price Updates Help". SIAM Journal on Discrete Mathematics. 10 (4): 551–572. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0895480194281185">10.1137/S0895480194281185</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0895-4801">0895-4801</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFOrlinAhuja1992" class="citation journal cs1">Orlin, James B.; Ahuja, Ravindra K. (1992-02-01). "New scaling algorithms for the assignment and minimum mean cycle problems". Mathematical Programming. 54 (1–3): 41–56. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01586040">10.1007/BF01586040</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0025-5610">0025-5610</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18213947">18213947</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFAlfaroPerezValenciaVargas2022" class="citation journal cs1">Alfaro, Carlos A.; Perez, Sergio L.; Valencia, Carlos E.; Vargas, Marcos C. (2022-06-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/s11590-021-01791-4">"The assignment problem revisited"</a>. Optimization Letters. 16 (5): 1531–1548. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs11590-021-01791-4">10.1007/s11590-021-01791-4</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1862-4480">1862-4480</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:238644205">238644205</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFMulmuleyVaziraniVazirani1987" class="citation journal cs1"><a href="Ketan_Mulmuley" title="Ketan Mulmuley">Mulmuley, Ketan</a>; <a href="Umesh_Vazirani" title="Umesh Vazirani">Vazirani, Umesh</a>; <a href="Vijay_Vazirani" title="Vijay Vazirani">Vazirani, Vijay</a> (1987). "Matching is as easy as matrix inversion". Combinatorica. 7 (1): 105–113. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02579206">10.1007/BF02579206</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:47370049">47370049</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFDuanPettie2014" class="citation journal cs1">Duan, Ran; Pettie, Seth (2014-01-01). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/2529989">"Linear-Time Approximation for Maximum Weight Matching"</a>. Journal of the ACM. 61: 1–23. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2529989">10.1145/2529989</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207208641">207208641</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFZhuLiuZhangZhu2016" class="citation journal cs1">Zhu, Haibin; Liu, Dongning; Zhang, Siqin; Zhu, Yu; Teng, Luyao; Teng, Shaohua (2016-03-07). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/S0304397516000037">"Solving the Many to Many assignment problem by improving the Kuhn–Munkres algorithm with backtracking"</a>. Theoretical Computer Science. 618: 30–41. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2016.01.002">10.1016/j.tcs.2016.01.002</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0304-3975">0304-3975</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFD.W." class="citation web cs1">D.W. <a rel="nofollow" class="external text" href="https://cs.stackexchange.com/questions/161149/high-multiplicity-maximum-weight-matching/161151#161151">"High-multiplicity maximum-weight matching"</a>. Computer Science Stack Exchange. Retrieved 2025-01-15.</cite>

</li>

</ol></div></div>

<ul><li><cite id="CITEREFBrualdi2006" class="citation book cs1">Brualdi, Richard A. (2006). <a rel="nofollow" class="external text" href="https://archive.org/details/combinatorialmat0000brua">Combinatorial matrix classes</a>. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-86565-4</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1106.05001">1106.05001</a>.</cite></li>

<li><cite id="CITEREFBurkardM._Dell'AmicoS._Martello2012" class="citation book cs1"><a href="Rainer_Burkard" title="Rainer Burkard">Burkard, Rainer</a>; M. Dell'Amico; S. Martello (2012). Assignment Problems (Revised reprint). SIAM. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-61197-222-1</bdi>.</cite></li>

<li><cite id="CITEREFBertsekas1998" class="citation book cs1"><a href="Dimitri_Bertsekas" title="Dimitri Bertsekas">Bertsekas, Dimitri</a> (1998). Network Optimization: Continuous and Discrete Models. Athena Scientific. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-886529-02-1</bdi>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q620614#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata644" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q620614#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata644" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh00004835">United States</a></li><li><a rel="nofollow" class="external text" href="https://www.nli.org.il/en/authorities/987007290944005171">Israel</a></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/concept/6ce6ef89-232c-4916-9d4d-d11e1557971d">Yale LUX</a></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-21" href="https://en.wikipedia.org/wiki/?title=Assignment_problem&oldid=1301763046">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>